#include <iostream>
#include <vector>
#include <string>
using namespace std;

#define endl '\n';

void solve(string s1,string s2)
{
    int m = s1.size(),n = s2.size();
    vector<vector<int>> dp(m+1,vector<int>(n+1));
    for(int i = 1;i<=m;++i)
    {
        for(int j = 1;j<=n;++j)
        {
            if(s1[i-1] == s2[j-1])
            {
                dp[i][j] = dp[i-1][j-1]+1;
            }
            else
            {
                dp[i][j] = max(dp[i-1][j],dp[i][j-1]);
            }

        }
    }
    cout<<"solve:"<<endl;
    cout<<dp[m][n]<<endl;

}

int main()
{
    string s1 = "ATCTGAT";
    string s2 = "TGGATA";
    solve(s1,s2);

    return 0;
}
